package algorithm;

import java.util.*;

public class T00773 {

    public static void main(String[] args) {
        int[][] board = {{1,2,3},{4,0,5}};
        System.out.println(new Solution().slidingPuzzle(board));
    }

    static class Solution {
        public int slidingPuzzle(int[][] board) {
            int n = board.length, m = board[0].length;
            String target = "123450";
            int[][] negs = calcNegs(n, m);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    sb.append(board[i][j]);
                }
            }
            Set<String> visited = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            queue.offer(sb.toString());
            visited.add(sb.toString());
            int step = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String cur = queue.poll();
                    if (target.equals(cur)) return step;
                    int zIndex = cur.indexOf("0");
                    for (int neg : negs[zIndex]) {
                        String s = swap(cur.toCharArray(), zIndex, neg);
                        if (!visited.contains(s)) {
                            visited.add(s);
                            queue.offer(s);
                        }
                    }
                }
                step ++;
            }
            return -1;
        }

        private String swap(char[] charArray, int zIndex, int neg) {
            char t = charArray[zIndex];
            charArray[zIndex] = charArray[neg];
            charArray[neg] = t;
            return new String(charArray);
        }

        public int[][] calcNegs(int n, int m) {
            int[][] negs = new int[n * m][];
            for (int i = 0; i < negs.length; i++) {
                List<Integer> list = new ArrayList<>();
                int left = i - 1;
                int right = i + 1;
                int up = i - m;
                int down = i + m;
                if (i % m != 0) list.add(left);
                if (i % m != m -1 && right < negs.length) list.add(right);
                if (up >= 0 && up < negs.length) list.add(up);
                if (down >= 0 && down < negs.length) list.add(down);
                negs[i] = list.stream().mapToInt(Integer::intValue).toArray();
            }
            return negs;
        }
    }
}
